public class Solution174 {
    public int calculateMinimumHP(int[][] dungeon) {
        int l=1,r=Integer.MAX_VALUE;
        int ans=-1;
        while (l<=r){
            int mid=l+(r-l)/2;
            if (check(dungeon,mid)){
                ans=mid;
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return ans;
    }

    private boolean check(int[][] f, int mid) {
        int m=f.length,n=f[0].length;
        int[][] g=new int[m][n];
        g[0][0]=f[0][0]+mid;
        for (int i=1;i<m;i++){
            g[i][0]=g[i-1][0]<=0?0:g[i-1][0]+f[i][0];
        }
        for (int i=1;i<n;i++){
            g[0][i]=g[0][i-1]<=0?0:g[0][i-1]+f[0][i];
        }
        for (int i=1;i<m;i++){
            for (int j=1;j<n;j++){
                int one= Math.max(g[i - 1][j], 0);
                int two= Math.max(g[i][j - 1], 0);
                int max= Math.max(one,two);
                g[i][j]=max<=0?0:max+f[i][j];
            }
        }
        return g[m-1][n-1]>0;
    }

    public static void main(String[] args) {
        System.out.println(new Solution174().calculateMinimumHP(new int[][]{{-2,-3,3},{-5,-10,1},{10,30,-5}}));
    }
}
